Queuing is an important aspect of virtually all data networking equipment. This is especially so for bridges and routers that make up local area networks (LANs), metropolitan area networks (MANs), and wide area networks (WANs). Design goals for queue managers include management of a large number of queues in the face of very high network packet rates with a minimized amount of logic and memory necessary to manage the queues. Design goals seek to avoid problems such as head of line blocking and to enable features such as per-queue policing and rate shaping which enable the enforcement and delivery of specific service levels.
A queue manager schedules storage and retrieval of packet data in queues. The queue manager or a scheduler module of the queue manager is tasked with metering the number of packet bytes transmitted from each queue per time unit for achieving a certain data rate. This time unit can represent a queue service interval. As packets vary in size, the scheduler has to determine for each service interval how many of the next packets are to be serviced to satisfy the bytes/interval criteria. The number of packets and, therefore, the number of operations per interval vary, thus resulting in a variable number of operations for a given rate. Furthermore, in conventional systems, the queue manager schedules the next queue service interval to be proportional to the length of the packet just dequeued even though the next packet may significantly differ in size. This complicates the scheduling process.
In conventional systems servicing multicast packets, the scheduler performs the multicast replications thus causing undesirable head of line blocking.
It is desirable to decrease the number of operations performed by a queue manager in managing queues. For example, it is desirable, to provide a basis for scheduling the next queue service with less size variability than that achieved, for example, by the length of the packet just dequeued. It is also desirable to decrease head of line blocking at the scheduler when multicast packets are replicated.